home *** CD-ROM | disk | FTP | other *** search
/ HPAVC / HPAVC CD-ROM.iso / pc / FAQSYS18.ZIP / FAQS.DAT / QUANTIZE.C < prev    next >
Encoding:
Text File  |  1996-08-18  |  58.6 KB  |  1,681 lines
  1. /*
  2. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
  3. %                                                                             %
  4. %                                                                             %
  5. %                                                                             %
  6. %           QQQ   U   U   AAA   N   N  TTTTT  IIIII   ZZZZZ  EEEEE            %
  7. %          Q   Q  U   U  A   A  NN  N    T      I        ZZ  E                %
  8. %          Q   Q  U   U  AAAAA  N N N    T      I      ZZZ   EEEEE            %
  9. %          Q  QQ  U   U  A   A  N  NN    T      I     ZZ     E                %
  10. %           QQQQ   UUU   A   A  N   N    T    IIIII   ZZZZZ  EEEEE            %
  11. %                                                                             %
  12. %                                                                             %
  13. %              Reduce the Number of Unique Colors in an Image                 %
  14. %                                                                             %
  15. %                                                                             %
  16. %                                                                             %
  17. %                           Software Design                                   %
  18. %                             John Cristy                                     %
  19. %                              July 1992                                      %
  20. %                                                                             %
  21. %  Copyright 1994 E. I. du Pont de Nemours and Company                        %
  22. %                                                                             %
  23. %  Permission to use, copy, modify, distribute, and sell this software and    %
  24. %  its documentation for any purpose is hereby granted without fee,           %
  25. %  provided that the above Copyright notice appear in all copies and that     %
  26. %  both that Copyright notice and this permission notice appear in            %
  27. %  supporting documentation, and that the name of E. I. du Pont de Nemours    %
  28. %  and Company not be used in advertising or publicity pertaining to          %
  29. %  distribution of the software without specific, written prior               %
  30. %  permission.  E. I. du Pont de Nemours and Company makes no representations %
  31. %  about the suitability of this software for any purpose.  It is provided    %
  32. %  "as is" without express or implied warranty.                               %
  33. %                                                                             %
  34. %  E. I. du Pont de Nemours and Company disclaims all warranties with regard  %
  35. %  to this software, including all implied warranties of merchantability      %
  36. %  and fitness, in no event shall E. I. du Pont de Nemours and Company be     %
  37. %  liable for any special, indirect or consequential damages or any           %
  38. %  damages whatsoever resulting from loss of use, data or profits, whether    %
  39. %  in an action of contract, negligence or other tortuous action, arising     %
  40. %  out of or in connection with the use or performance of this software.      %
  41. %                                                                             %
  42. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
  43. %
  44. %  Realism in computer graphics typically requires using 24 bits/pixel to
  45. %  generate an image.  Yet many graphic display devices do not contain
  46. %  the amount of memory necessary to match the spatial and color
  47. %  resolution of the human eye.  The QUANTIZE program takes a 24 bit
  48. %  image and reduces the number of colors so it can be displayed on
  49. %  raster device with less bits per pixel.  In most instances, the
  50. %  quantized image closely resembles the original reference image.
  51. %
  52. %  A reduction of colors in an image is also desirable for image
  53. %  transmission and real-time animation.
  54. %
  55. %  Function Quantize takes a standard RGB or monochrome images and quantizes
  56. %  them down to some fixed number of colors.
  57. %
  58. %  For purposes of color allocation, an image is a set of n pixels, where
  59. %  each pixel is a point in RGB space.  RGB space is a 3-dimensional
  60. %  vector space, and each pixel, pi,  is defined by an ordered triple of
  61. %  red, green, and blue coordinates, (ri, gi, bi).
  62. %
  63. %  Each primary color component (red, green, or blue) represents an
  64. %  intensity which varies linearly from 0 to a maximum value, cmax, which
  65. %  corresponds to full saturation of that color.  Color allocation is
  66. %  defined over a domain consisting of the cube in RGB space with
  67. %  opposite vertices at (0,0,0) and (cmax,cmax,cmax).  QUANTIZE requires
  68. %  cmax = 255.
  69. %
  70. %  The algorithm maps this domain onto a tree in which each node
  71. %  represents a cube within that domain.  In the following discussion
  72. %  these cubes are defined by the coordinate of two opposite vertices:
  73. %  The vertex nearest the origin in RGB space and the vertex farthest
  74. %  from the origin.
  75. %
  76. %  The tree's root node represents the the entire domain, (0,0,0) through
  77. %  (cmax,cmax,cmax).  Each lower level in the tree is generated by
  78. %  subdividing one node's cube into eight smaller cubes of equal size.
  79. %  This corresponds to bisecting the parent cube with planes passing
  80. %  through the midpoints of each edge.
  81. %
  82. %  The basic algorithm operates in three phases: Classification,
  83. %  Reduction, and Assignment.  Classification builds a color
  84. %  description tree for the image.  Reduction collapses the tree until
  85. %  the number it represents, at most, the number of colors desired in the
  86. %  output image.  Assignment defines the output image's color map and
  87. %  sets each pixel's color by reclassification in the reduced tree.
  88. %
  89. %  Classification begins by initializing a color description tree of
  90. %  sufficient depth to represent each possible input color in a leaf.
  91. %  However, it is impractical to generate a fully-formed color
  92. %  description tree in the classification phase for realistic values of
  93. %  cmax.  If colors components in the input image are quantized to k-bit
  94. %  precision, so that cmax= 2k-1, the tree would need k levels below the
  95. %  root node to allow representing each possible input color in a leaf.
  96. %  This becomes prohibitive because the tree's total number of nodes is
  97. %  1 + sum(i=1,k,8k).
  98. %
  99. %  A complete tree would require 19,173,961 nodes for k = 8, cmax = 255.
  100. %  Therefore, to avoid building a fully populated tree, QUANTIZE: (1)
  101. %  Initializes data structures for nodes only as they are needed;  (2)
  102. %  Chooses a maximum depth for the tree as a function of the desired
  103. %  number of colors in the output image (currently log2(colormap size)).
  104. %
  105. %  For each pixel in the input image, classification scans downward from
  106. %  the root of the color description tree.  At each level of the tree it
  107. %  identifies the single node which represents a cube in RGB space
  108. %  containing the pixel's color.  It updates the following data for each
  109. %  such node:
  110. %
  111. %    n1 : Number of pixels whose color is contained in the RGB cube
  112. %    which this node represents;
  113. %
  114. %    n2 : Number of pixels whose color is not represented in a node at
  115. %    lower depth in the tree;  initially,  n2 = 0 for all nodes except
  116. %    leaves of the tree.
  117. %
  118. %    Sr, Sg, Sb : Sums of the red, green, and blue component values for
  119. %    all pixels not classified at a lower depth. The combination of
  120. %    these sums and n2  will ultimately characterize the mean color of a
  121. %    set of pixels represented by this node.
  122. %
  123. %  Reduction repeatedly prunes the tree until the number of nodes with
  124. %  n2 > 0 is less than or equal to the maximum number of colors allowed
  125. %  in the output image.  On any given iteration over the tree, it selects
  126. %  those nodes whose n1  count is minimal for pruning and merges their
  127. %  color statistics upward. It uses a pruning threshold, ns, to govern
  128. %  node selection as follows:
  129. %
  130. %    ns = 0
  131. %    while number of nodes with (n2 > 0) > required maximum number of colors
  132. %      prune all nodes such that n1 <= ns
  133. %      Set ns to minimum n1 in remaining nodes
  134. %
  135. %  When a node to be pruned has offspring, the pruning procedure invokes
  136. %  itself recursively in order to prune the tree from the leaves upward.
  137. %  n2,  Sr, Sg,  and  Sb in a node being pruned are always added to the
  138. %  corresponding data in that node's parent.  This retains the pruned
  139. %  node's color characteristics for later averaging.
  140. %
  141. %  For each node, n2 pixels exist for which that node represents the
  142. %  smallest volume in RGB space containing those pixel's colors.  When n2
  143. %  > 0 the node will uniquely define a color in the output image. At the
  144. %  beginning of reduction,  n2 = 0  for all nodes except a the leaves of
  145. %  the tree which represent colors present in the input image.
  146. %
  147. %  The other pixel count, n1, indicates the total number of colors
  148. %  within the cubic volume which the node represents.  This includes n1 -
  149. %  n2  pixels whose colors should be defined by nodes at a lower level in
  150. %  the tree.
  151. %
  152. %  Assignment generates the output image from the pruned tree.  The
  153. %  output image consists of two parts: (1)  A color map, which is an
  154. %  array of color descriptions (RGB triples) for each color present in
  155. %  the output image;  (2)  A pixel array, which represents each pixel as
  156. %  an index into the color map array.
  157. %
  158. %  First, the assignment phase makes one pass over the pruned color
  159. %  description tree to establish the image's color map.  For each node
  160. %  with n2  > 0, it divides Sr, Sg, and Sb by n2 .  This produces the
  161. %  mean color of all pixels that classify no lower than this node.  Each
  162. %  of these colors becomes an entry in the color map.
  163. %
  164. %  Finally,  the assignment phase reclassifies each pixel in the pruned
  165. %  tree to identify the deepest node containing the pixel's color.  The
  166. %  pixel's value in the pixel array becomes the index of this node's mean
  167. %  color in the color map.
  168. %
  169. %  For efficiency, QUANTIZE requires that the reference image be in a
  170. %  run-length encoded format.
  171. %
  172. %  With the permission of USC Information Sciences Institute, 4676 Admiralty
  173. %  Way, Marina del Rey, California  90292, this code was adapted from module
  174. %  ALCOLS written by Paul Raveling.
  175. %
  176. %  The names of ISI and USC are not used in advertising or publicity
  177. %  pertaining to distribution of the software without prior specific
  178. %  written permission from ISI.
  179. %
  180. %
  181. */
  182.  
  183. /*
  184.   Include declarations.
  185. */
  186. #include "magick.h"
  187. #include "image.h"
  188.  
  189. /*
  190.   Define declarations.
  191. */
  192. #define color_number  number_colors
  193. #define MaxNodes  266817
  194. #define MaxShift  8
  195. #define MaxTreeDepth  8  /* Log2(MaxRGB) */
  196. #define NodesInAList  2048
  197.  
  198. /*
  199.   Structures.
  200. */
  201. typedef struct _Node
  202. {
  203.   struct _Node
  204.     *parent,
  205.     *child[8];
  206.  
  207.   unsigned char
  208.     id,
  209.     level,
  210.     census,
  211.     mid_red,
  212.     mid_green,
  213.     mid_blue;
  214.  
  215.   unsigned long
  216.     number_colors,
  217.     number_unique,
  218.     total_red,
  219.     total_green,
  220.     total_blue;
  221. } Node;
  222.  
  223. typedef struct _Nodes
  224. {
  225.   Node
  226.     nodes[NodesInAList];
  227.  
  228.   struct _Nodes
  229.     *next;
  230. } Nodes;
  231.  
  232. typedef struct _Cube
  233. {
  234.   Node
  235.     *root;
  236.  
  237.   ColorPacket
  238.     color,
  239.     *colormap;
  240.  
  241.   unsigned int
  242.     depth;
  243.  
  244.   unsigned long
  245.     colors,
  246.     pruning_threshold,
  247.     next_pruning_threshold,
  248.     distance,
  249.     squares[MaxRGB+MaxRGB+1];
  250.  
  251.   unsigned int
  252.     shift[MaxTreeDepth+1],
  253.     nodes,
  254.     free_nodes,
  255.     color_number;
  256.  
  257.   Node
  258.     *next_node;
  259.  
  260.   Nodes
  261.     *node_queue;
  262. } Cube;
  263.  
  264. /*
  265.   Global variables.
  266. */
  267. static Cube
  268.   cube;
  269.  
  270. /*
  271.   Forward declarations.
  272. */
  273. static Node
  274.   *InitializeNode _Declare((unsigned int,unsigned int,Node *,unsigned int,
  275.     unsigned int,unsigned int));
  276.  
  277. static unsigned int
  278.   DitherImage _Declare((Image *));
  279.  
  280. static void
  281.   ClosestColor _Declare((Node *)),
  282.   Colormap _Declare((Node *)),
  283.   PruneLevel _Declare((Node *));
  284.  
  285. /*
  286. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
  287. %                                                                             %
  288. %                                                                             %
  289. %                                                                             %
  290. %  A s s i g n m e n t                                                        %
  291. %                                                                             %
  292. %                                                                             %
  293. %                                                                             %
  294. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
  295. %
  296. %  Procedure Assignment generates the output image from the pruned tree.  The
  297. %  output image consists of two parts: (1)  A color map, which is an
  298. %  array of color descriptions (RGB triples) for each color present in
  299. %  the output image;  (2)  A pixel array, which represents each pixel as
  300. %  an index into the color map array.
  301. %
  302. %  First, the assignment phase makes one pass over the pruned color
  303. %  description tree to establish the image's color map.  For each node
  304. %  with n2  > 0, it divides Sr, Sg, and Sb by n2 .  This produces the
  305. %  mean color of all pixels that classify no lower than this node.  Each
  306. %  of these colors becomes an entry in the color map.
  307. %
  308. %  Finally,  the assignment phase reclassifies each pixel in the pruned
  309. %  tree to identify the deepest node containing the pixel's color.  The
  310. %  pixel's value in the pixel array becomes the index of this node's mean
  311. %  color in the color map.
  312. %
  313. %  The format of the Assignment routine is:
  314. %
  315. %      Assignment(image,number_colors,dither,colorspace)
  316. %
  317. %  A description of each parameter follows.
  318. %
  319. %    o image: Specifies a pointer to an Image structure;  returned from
  320. %      ReadImage.
  321. %
  322. %    o number_colors: This integer value indicates the maximum number of
  323. %      colors in the quantized image or colormap.  Here we use this value
  324. %      to determine the depth of the color description tree.
  325. %
  326. %    o dither: Set this integer value to something other than zero to
  327. %      dither the quantized image.  The basic strategy of dithering is to
  328. %      trade intensity resolution for spatial resolution by averaging the
  329. %      intensities of several neighboring pixels.  Images which suffer
  330. %      from severe contouring when quantized can be improved with the
  331. %      technique of dithering.  Severe contouring generally occurs when
  332. %      quantizing to very few colors, or to a poorly-chosen colormap.
  333. %      Note, dithering is a computationally expensive process and will
  334. %      increase processing time significantly.
  335. %
  336. %    o colorspace: An unsigned integer value that indicates the colorspace.
  337. %
  338. %
  339. */
  340. static void Assignment(image,number_colors,dither,colorspace)
  341. Image
  342.   *image;
  343.  
  344. unsigned int
  345.   number_colors,
  346.   dither,
  347.   colorspace;
  348. {
  349.   register int
  350.     i;
  351.  
  352.   register Node
  353.     *node;
  354.  
  355.   register RunlengthPacket
  356.     *p;
  357.  
  358.   register unsigned int
  359.     id;
  360.  
  361.   /*
  362.     Allocate image colormap.
  363.   */
  364.   if (image->colormap != (ColorPacket *) NULL)
  365.     (void) free((char *) image->colormap);
  366.   image->colormap=(ColorPacket *)
  367.     malloc((unsigned int) cube.colors*sizeof(ColorPacket));
  368.   if (image->colormap == (ColorPacket *) NULL)
  369.     {
  370.       Warning("Unable to quantize image","Memory allocation failed");
  371.       exit(1);
  372.     }
  373.   if (image->signature != (char *) NULL)
  374.     (void) free((char *) image->signature);
  375.   image->signature=(char *) NULL;
  376.   cube.colormap=image->colormap;
  377.   cube.colors=0;
  378.   Colormap(cube.root);
  379.   if ((number_colors == 2)  && (colorspace == GRAYColorspace))
  380.     {
  381.       unsigned int
  382.         polarity;
  383.  
  384.       /*
  385.         Monochrome image.
  386.       */
  387.       polarity=Intensity(image->colormap[0]) > Intensity(image->colormap[1]);
  388.       image->colormap[polarity].red=0;
  389.       image->colormap[polarity].green=0;
  390.       image->colormap[polarity].blue=0;
  391.       image->colormap[!polarity].red=MaxRGB;
  392.       image->colormap[!polarity].green=MaxRGB;
  393.       image->colormap[!polarity].blue=MaxRGB;
  394.     }
  395.   image->matte=False;
  396.   image->class=PseudoClass;
  397.   image->colors=(unsigned int) cube.colors;
  398.   /*
  399.     Create a reduced color image.
  400.   */
  401.   if (dither)
  402.     dither=!DitherImage(image);
  403.   p=image->pixels;
  404.   if (!dither)
  405.     for (i=0; i < image->packets; i++)
  406.     {
  407.       /*
  408.         Identify the deepest node containing the pixel's color.
  409.       */
  410.       node=cube.root;
  411.       for ( ; ; )
  412.       {
  413.         id=(p->red > node->mid_red ? 1 : 0) |
  414.           (p->green > node->mid_green ? 1 : 0) << 1 |
  415.          (p->blue > node->mid_blue ? 1 : 0) << 2;
  416.        if ((node->census & (1 << id)) == 0)
  417.          break;
  418.        node=node->child[id];
  419.      }
  420.      /*
  421.        Find closest color among siblings and their children.
  422.      */
  423.      cube.color.red=p->red;
  424.      cube.color.green=p->green;
  425.      cube.color.blue=p->blue;
  426.      cube.distance=(unsigned long) (~0);
  427.      ClosestColor(node->parent);
  428.      p->index=cube.color_number;
  429.      p++;
  430.    }
  431. }
  432.  
  433. /*
  434. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
  435. %                                                                             %
  436. %                                                                             %
  437. %                                                                             %
  438. %  C l a s s i f i c a t i o n                                                %
  439. %                                                                             %
  440. %                                                                             %
  441. %                                                                             %
  442. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
  443. %
  444. %  Procedure Classification begins by initializing a color description tree
  445. %  of sufficient depth to represent each possible input color in a leaf.
  446. %  However, it is impractical to generate a fully-formed color
  447. %  description tree in the classification phase for realistic values of
  448. %  cmax.  If colors components in the input image are quantized to k-bit
  449. %  precision, so that cmax= 2k-1, the tree would need k levels below the
  450. %  root node to allow representing each possible input color in a leaf.
  451. %  This becomes prohibitive because the tree's total number of nodes is
  452. %  1 + sum(i=1,k,8k).
  453. %
  454. %  A complete tree would require 19,173,961 nodes for k = 8, cmax = 255.
  455. %  Therefore, to avoid building a fully populated tree, QUANTIZE: (1)
  456. %  Initializes data structures for nodes only as they are needed;  (2)
  457. %  Chooses a maximum depth for the tree as a function of the desired
  458. %  number of colors in the output image (currently log2(colormap size)).
  459. %
  460. %  For each pixel in the input image, classification scans downward from
  461. %  the root of the color description tree.  At each level of the tree it
  462. %  identifies the single node which represents a cube in RGB space
  463. %  containing It updates the following data for each such node:
  464. %
  465. %    n1 : Number of pixels whose color is contained in the RGB cube
  466. %    which this node represents;
  467. %
  468. %    n2 : Number of pixels whose color is not represented in a node at
  469. %    lower depth in the tree;  initially,  n2 = 0 for all nodes except
  470. %    leaves of the tree.
  471. %
  472. %    Sr, Sg, Sb : Sums of the red, green, and blue component values for
  473. %    all pixels not classified at a lower depth. The combination of
  474. %    these sums and n2  will ultimately characterize the mean color of a
  475. %    set of pixels represented by this node.
  476. %
  477. %  The format of the Classification routine is:
  478. %
  479. %      Classification(image)
  480. %
  481. %  A description of each parameter follows.
  482. %
  483. %    o image: Specifies a pointer to an Image structure;  returned from
  484. %      ReadImage.
  485. %
  486. %
  487. */
  488. static void Classification(image)
  489. Image
  490.   *image;
  491. {
  492.   register int
  493.     i;
  494.  
  495.   register Node
  496.     *node;
  497.  
  498.   register RunlengthPacket
  499.     *p;
  500.  
  501.   register unsigned int
  502.     bisect,
  503.     count,
  504.     id,
  505.     level;
  506.  
  507.   p=image->pixels;
  508.   for (i=0; i < image->packets; i++)
  509.   {
  510.     if (cube.nodes > MaxNodes)
  511.       {
  512.         /*
  513.           Prune one level if the color tree is too large.
  514.         */
  515.         PruneLevel(cube.root);
  516.         cube.depth--;
  517.       }
  518.     /*
  519.       Start at the root and descend the color cube tree.
  520.     */
  521.     count=p->length+1;
  522.     node=cube.root;
  523.     for (level=1; level <= cube.depth; level++)
  524.     {
  525.       id=(p->red > node->mid_red ? 1 : 0) |
  526.         (p->green > node->mid_green ? 1 : 0) << 1 |
  527.         (p->blue > node->mid_blue ? 1 : 0) << 2;
  528.       if (node->child[id] == (Node *) NULL)
  529.         {
  530.           /*
  531.             Set colors of new node to contain pixel.
  532.           */
  533.           node->census|=1 << id;
  534.           bisect=(unsigned int) (1 << (MaxTreeDepth-level)) >> 1;
  535.           node->child[id]=InitializeNode(id,level,node,
  536.             node->mid_red+(id & 1 ? bisect : -bisect),
  537.             node->mid_green+(id & 2 ? bisect : -bisect),
  538.             node->mid_blue+(id & 4 ? bisect : -bisect));
  539.           if (node->child[id] == (Node *) NULL)
  540.             {
  541.               Warning("Unable to quantize image","Memory allocation failed");
  542.               exit(1);
  543.             }
  544.           if (level == cube.depth)
  545.             cube.colors++;
  546.         }
  547.       /*
  548.         Record the number of colors represented by this node.  Shift by level
  549.         in the color description tree.
  550.       */
  551.       node=node->child[id];
  552.       node->number_colors+=count << cube.shift[level];
  553.     }
  554.     /*
  555.       Increment unique color count and sum RGB values for this leaf for later
  556.       derivation of the mean cube color.
  557.     */
  558.     node->number_unique+=count;
  559.     node->total_red+=p->red*count;
  560.     node->total_green+=p->green*count;
  561.     node->total_blue+=p->blue*count;
  562.     p++;
  563.   }
  564. }
  565.  
  566. /*
  567. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
  568. %                                                                             %
  569. %                                                                             %
  570. %                                                                             %
  571. %  C l o s e s t C o l o r                                                    %
  572. %                                                                             %
  573. %                                                                             %
  574. %                                                                             %
  575. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
  576. %
  577. %  Procedure ClosestColor traverses the color cube tree at a particular node
  578. %  and determines which colormap entry best represents the input color.
  579. %
  580. %  The format of the ClosestColor routine is:
  581. %
  582. %      ClosestColor(node)
  583. %
  584. %  A description of each parameter follows.
  585. %
  586. %    o node: The address of a structure of type Node which points to a
  587. %      node in the color cube tree that is to be pruned.
  588. %
  589. %
  590. */
  591. static void ClosestColor(node)
  592. register Node
  593.   *node;
  594. {
  595.   register unsigned int
  596.     id;
  597.  
  598.   /*
  599.     Traverse any children.
  600.   */
  601.   if (node->census != 0)
  602.     for (id=0; id < 8; id++)
  603.       if (node->census & (1 << id))
  604.         ClosestColor(node->child[id]);
  605.   if (node->number_unique != 0)
  606.     {
  607.       register ColorPacket
  608.         *color;
  609.  
  610.       register unsigned int
  611.         blue_distance,
  612.         green_distance,
  613.         red_distance;
  614.  
  615.       register unsigned long
  616.         distance;
  617.  
  618.       /*
  619.         Determine if this color is "closest".
  620.       */
  621.       color=cube.colormap+node->color_number;
  622.       red_distance=(int) color->red-(int) cube.color.red+MaxRGB;
  623.       green_distance=(int) color->green-(int) cube.color.green+MaxRGB;
  624.       blue_distance=(int) color->blue-(int) cube.color.blue+MaxRGB;
  625.       distance=cube.squares[red_distance]+cube.squares[green_distance]+
  626.         cube.squares[blue_distance];
  627.       if (distance < cube.distance)
  628.         {
  629.           cube.distance=distance;
  630.           cube.color_number=(unsigned short) node->color_number;
  631.         }
  632.     }
  633. }
  634.  
  635. /*
  636. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
  637. %                                                                             %
  638. %                                                                             %
  639. %                                                                             %
  640. %  C o l o r m a p                                                            %
  641. %                                                                             %
  642. %                                                                             %
  643. %                                                                             %
  644. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
  645. %
  646. %  Procedure Colormap traverses the color cube tree and notes each colormap
  647. %  entry.  A colormap entry is any node in the color cube tree where the
  648. %  number of unique colors is not zero.
  649. %
  650. %  The format of the Colormap routine is:
  651. %
  652. %      Colormap(node)
  653. %
  654. %  A description of each parameter follows.
  655. %
  656. %    o node: The address of a structure of type Node which points to a
  657. %      node in the color cube tree that is to be pruned.
  658. %
  659. %
  660. */
  661. static void Colormap(node)
  662. register Node
  663.   *node;
  664. {
  665.   register unsigned int
  666.     id;
  667.  
  668.   /*
  669.     Traverse any children.
  670.   */
  671.   if (node->census != 0)
  672.     for (id=0; id < 8; id++)
  673.       if (node->census & (1 << id))
  674.         Colormap(node->child[id]);
  675.   if (node->number_unique != 0)
  676.     {
  677.       /*
  678.         Colormap entry is defined by the mean color in this cube.
  679.       */
  680.       cube.colormap[cube.colors].red=(unsigned char)
  681.         ((node->total_red+(node->number_unique >> 1))/node->number_unique);
  682.       cube.colormap[cube.colors].green=(unsigned char)
  683.         ((node->total_green+(node->number_unique >> 1))/node->number_unique);
  684.       cube.colormap[cube.colors].blue=(unsigned char)
  685.         ((node->total_blue+(node->number_unique >> 1))/node->number_unique);
  686.       node->color_number=cube.colors++;
  687.     }
  688. }
  689.  
  690. /*
  691. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
  692. %                                                                             %
  693. %                                                                             %
  694. %                                                                             %
  695. %  D i t h e r I m a g e                                                      %
  696. %                                                                             %
  697. %                                                                             %
  698. %                                                                             %
  699. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
  700. %
  701. %  Procedure DitherImage uses the Floyd-Steinberg algorithm to dither the
  702. %  image.  Refer to "An Adaptive Algorithm for Spatial GreySscale", Robert W.
  703. %  Floyd and Louis Steinberg, Proceedings of the S.I.D., Volume 17(2), 1976.
  704. %
  705. %  First find the closest representation to the reference pixel color in the
  706. %  colormap, the node pixel is assigned this color.  Next, the colormap color
  707. %  is subtracted from the reference pixels color, this represents the
  708. %  quantization error.  Various amounts of this error are added to the pixels
  709. %  ahead and below the node pixel to correct for this error.  The error
  710. %  proportions are:
  711. %
  712. %            P     7/16
  713. %      3/16  5/16  1/16
  714. %
  715. %  The error is distributed left-to-right for even scanlines and right-to-left
  716. %  for odd scanlines.
  717. %
  718. %  The format of the DitherImage routine is:
  719. %
  720. %      DitherImage(image)
  721. %
  722. %  A description of each parameter follows.
  723. %
  724. %    o image: Specifies a pointer to an Image structure;  returned from
  725. %      ReadImage.
  726. %
  727. %
  728. */
  729. static unsigned int DitherImage(image)
  730. Image
  731.   *image;
  732. {
  733.   typedef struct _ErrorPacket
  734.   {
  735.     int
  736.       red,
  737.       green,
  738.       blue;
  739.   } ErrorPacket;
  740.  
  741.   ErrorPacket
  742.     *error;
  743.  
  744.   int
  745.     *cache,
  746.     step;
  747.  
  748.   Node
  749.     *node;
  750.  
  751.   register int
  752.     i,
  753.     blue_error,
  754.     *error_limit,
  755.     green_error,
  756.     red_error;
  757.  
  758.   register RunlengthPacket
  759.     *q;
  760.  
  761.   register ErrorPacket
  762.     *cs,
  763.     *ns;
  764.  
  765.   register unsigned char
  766.     *range_limit;
  767.  
  768.   unsigned char
  769.     blue,
  770.     green,
  771.     red;
  772.  
  773.   unsigned int
  774.     id,
  775.     quantum,
  776.     x,
  777.     y;
  778.  
  779.   unsigned short
  780.     index;
  781.  
  782.   /*
  783.     Image must be uncompressed.
  784.   */
  785.   if (!UncompressImage(image))
  786.     return(True);
  787.   /*
  788.     Allocate memory.
  789.   */
  790.   cache=(int *) malloc((1 << 18)*sizeof(int));
  791.   error=(ErrorPacket *) malloc(((image->columns+2) << 1)*sizeof(ErrorPacket));
  792.   error_limit=(int *) malloc((MaxRGB*2+1)*sizeof(int));
  793.   range_limit=(unsigned char *) malloc(3*(MaxRGB+1)*sizeof(unsigned char));
  794.   if ((cache == (int *) NULL) || (error == (ErrorPacket *) NULL) ||
  795.       (error_limit == (int *) NULL) || (range_limit == (unsigned char *) NULL))
  796.     {
  797.       Warning("Unable to dither image","Memory allocation failed");
  798.       return(True);
  799.     }
  800.   /*
  801.     Initialize color cache.
  802.   */
  803.   for (i=0; i < (1 << 18); i++)
  804.     cache[i]=(-1);
  805.   /*
  806.     Initialize error tables.
  807.   */
  808.   for (i=0; i < ((image->columns+2) << 1); i++)
  809.   {
  810.     error[i].red=0;
  811.     error[i].green=0;
  812.     error[i].blue=0;
  813.   }
  814.   /*
  815.     Initialize error limit (constrain error).
  816.   */
  817.   quantum=Max(image->colors >> 4,1);
  818.   error_limit+=MaxRGB;
  819.   step=0;
  820.   for (i=0; i < ((MaxRGB+1)/quantum); i++)
  821.   {
  822.     error_limit[i]=step;
  823.     error_limit[-i]=(-step);
  824.     step++;
  825.   }
  826.   if (quantum > 3)
  827.     for ( ; i < (3*(MaxRGB+1)/quantum); i++)
  828.     {
  829.       error_limit[i]=step;
  830.       error_limit[-i]=(-step);
  831.       step+=(i & 0x01) ? 0 : 1;
  832.     }
  833.   for ( ; i <= MaxRGB; i++)
  834.   {
  835.     error_limit[i]=step;
  836.     error_limit[-i]=(-step);
  837.   }
  838.   /*
  839.     Initialize range tables.
  840.   */
  841.   for (i=0; i <= MaxRGB; i++)
  842.   {
  843.     range_limit[i]=0;
  844.     range_limit[i+(MaxRGB+1)]=(unsigned char) i;
  845.     range_limit[i+(MaxRGB+1)*2]=MaxRGB;
  846.   }
  847.   range_limit+=(MaxRGB+1);
  848.   /*
  849.     Dither image.
  850.   */
  851.   for (y=0; y < image->rows; y++)
  852.   {
  853.     q=image->pixels+image->columns*y;
  854.     cs=error+1;
  855.     ns=cs+image->columns+2;
  856.     step=y & 0x01 ? -1 : 1;
  857.     if (step < 0)
  858.       {
  859.         /*
  860.           Distribute error right-to-left for odd scanlines.
  861.         */
  862.         q+=(image->columns-1);
  863.         ns=error+image->columns;
  864.         cs=ns+image->columns+2;
  865.       }
  866.     for (x=0; x < image->columns; x++)
  867.     {
  868.       red_error=error_limit[(cs->red+8)/16];
  869.       green_error=error_limit[(cs->green+8)/16];
  870.       blue_error=error_limit[(cs->blue+8)/16];
  871.       red=range_limit[(int) q->red+red_error];
  872.       green=range_limit[(int) q->green+green_error];
  873.       blue=range_limit[(int) q->blue+blue_error];
  874.       i=(blue >> 2) << 12 | (green >> 2) << 6 | red >> 2;
  875.       if (cache[i] < 0)
  876.         {
  877.           /*
  878.             Identify the deepest node containing the pixel's color.
  879.           */
  880.           node=cube.root;
  881.           for ( ; ; )
  882.           {
  883.             id=(red > node->mid_red ? 1 : 0) |
  884.               (green > node->mid_green ? 1 : 0) << 1 |
  885.               (blue > node->mid_blue ? 1 : 0) << 2;
  886.             if ((node->census & (1 << id)) == 0)
  887.               break;
  888.             node=node->child[id];
  889.           }
  890.           /*
  891.             Find closest color among siblings and their children.
  892.           */
  893.           cube.color.red=red;
  894.           cube.color.green=green;
  895.           cube.color.blue=blue;
  896.           cube.distance=(unsigned long) (~0);
  897.           ClosestColor(node->parent);
  898.           cache[i]=cube.color_number;
  899.         }
  900.       index=(unsigned short) cache[i];
  901.       red_error=(int) red-(int) cube.colormap[index].red;
  902.       green_error=(int) green-(int) cube.colormap[index].green;
  903.       blue_error=(int) blue-(int) cube.colormap[index].blue;
  904.       q->index=index;
  905.       q+=step;
  906.       /*
  907.         Propagate the error in these proportions:
  908.                 Q     7/16
  909.           3/16  5/16  1/16
  910.       */
  911.       cs->red=0;
  912.       cs->green=0;
  913.       cs->blue=0;
  914.       cs+=step;
  915.       cs->red+=7*red_error;
  916.       cs->green+=7*green_error;
  917.       cs->blue+=7*blue_error;
  918.       ns-=step;
  919.       ns->red+=3*red_error;
  920.       ns->green+=3*green_error;
  921.       ns->blue+=3*blue_error;
  922.       ns+=step;
  923.       ns->red+=5*red_error;
  924.       ns->green+=5*green_error;
  925.       ns->blue+=5*blue_error;
  926.       ns+=step;
  927.       ns->red+=red_error;
  928.       ns->green+=green_error;
  929.       ns->blue+=blue_error;
  930.     }
  931.   }
  932.   /*
  933.     Free up memory.
  934.   */
  935.   range_limit-=(MaxRGB+1);
  936.   (void) free((char *) range_limit);
  937.   error_limit-=MaxRGB;
  938.   (void) free((char *) error_limit);
  939.   (void) free((char *) error);
  940.   (void) free((char *) cache);
  941.   return(False);
  942. }
  943.  
  944. /*
  945. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
  946. %                                                                             %
  947. %                                                                             %
  948. %                                                                             %
  949. %  I n i t i a l i z e C u b e                                                %
  950. %                                                                             %
  951. %                                                                             %
  952. %                                                                             %
  953. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
  954. %
  955. %  Function InitializeCube initialize the Cube data structure.
  956. %
  957. %  The format of the InitializeCube routine is:
  958. %
  959. %      InitializeCube(number_pixels,number_colors,tree_depth,adjust)
  960. %
  961. %  A description of each parameter follows.
  962. %
  963. %    o number_pixels: Specifies the number of individual pixels in the image.
  964. %
  965. %    o number_colors: This integer value indicates the maximum number of
  966. %      colors in the quantized image or colormap.  Here we use this value
  967. %      to determine the depth of the color description tree.
  968. %
  969. %    o tree_depth: Normally, this integer value is zero or one.  A zero or
  970. %      one tells Quantize to choose a optimal tree depth of Log4(number_colors).
  971. %      A tree of this depth generally allows the best representation of the
  972. %      reference image with the least amount of memory and the fastest
  973. %      computational speed.  In some cases, such as an image with low color
  974. %      dispersion (a few number of colors), a value other than
  975. %      Log4(number_colors) is required.  To expand the color tree completely,
  976. %      use a value of 8.
  977. %
  978. %    o adjust: An unsigned integer used to adjust the tree depth.
  979. %
  980. */
  981. static void InitializeCube(number_pixels,number_colors,tree_depth,adjust)
  982. unsigned int
  983.   number_pixels,
  984.   number_colors,
  985.   tree_depth,
  986.   adjust;
  987. {
  988.   char
  989.     c;
  990.  
  991.   register int
  992.     i;
  993.  
  994.   unsigned int
  995.     bits,
  996.     level,
  997.     max_shift;
  998.  
  999.   /*
  1000.     Initialize tree to describe color cube.  Depth is: Log4(colormap size)+2;
  1001.   */
  1002.   cube.node_queue=(Nodes *) NULL;
  1003.   cube.nodes=0;
  1004.   cube.free_nodes=0;
  1005.   if (tree_depth == 0)
  1006.     {
  1007.       for (tree_depth=1; number_colors != 0; tree_depth++)
  1008.         number_colors>>=2;
  1009.       if (tree_depth > adjust)
  1010.         tree_depth-=adjust;
  1011.     }
  1012.   cube.depth=tree_depth;
  1013.   if (cube.depth > 8)
  1014.     cube.depth=8;
  1015.   if (cube.depth < 2)
  1016.     cube.depth=2;
  1017.   /*
  1018.     Initialize the shift values.
  1019.   */
  1020.   c=1;
  1021.   for (bits=0; c != (char) 0; bits++)
  1022.     c<<=1;
  1023.   for (max_shift=sizeof(unsigned int)*bits; number_pixels != 0; max_shift--)
  1024.     number_pixels>>=1;
  1025.   for (level=0; level <= cube.depth; level++)
  1026.   {
  1027.     cube.shift[level]=max_shift;
  1028.     if (max_shift != 0)
  1029.       max_shift--;
  1030.   }
  1031.   /*
  1032.     Initialize root node.
  1033.   */
  1034.   cube.root=InitializeNode(0,0,(Node *) NULL,(MaxRGB+1) >> 1,(MaxRGB+1) >> 1,
  1035.     (MaxRGB+1) >> 1);
  1036.   if (cube.root == (Node *) NULL)
  1037.     {
  1038.       Warning("Unable to quantize image","Memory allocation failed");
  1039.       exit(1);
  1040.     }
  1041.   cube.root->parent=cube.root;
  1042.   cube.root->number_colors=(unsigned long) (~0);
  1043.   cube.colors=0;
  1044.   /*
  1045.     Initialize the square values.
  1046.   */
  1047.   for (i=(-MaxRGB); i <= MaxRGB; i++)
  1048.     cube.squares[i+MaxRGB]=i*i;
  1049. }
  1050.  
  1051. /*
  1052. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
  1053. %                                                                             %
  1054. %                                                                             %
  1055. %                                                                             %
  1056. %  I n i t i a l i z e N o d e                                                %
  1057. %                                                                             %
  1058. %                                                                             %
  1059. %                                                                             %
  1060. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
  1061. %
  1062. %  Function InitializeNode allocates memory for a new node in the color cube
  1063. %  tree and presets all fields to zero.
  1064. %
  1065. %  The format of the InitializeNode routine is:
  1066. %
  1067. %      node=InitializeNode(node,id,level,mid_red,mid_green,mid_blue)
  1068. %
  1069. %  A description of each parameter follows.
  1070. %
  1071. %    o node: The InitializeNode routine returns this integer address.
  1072. %
  1073. %    o id: Specifies the child number of the node.
  1074. %
  1075. %    o level: Specifies the level in the classification the node resides.
  1076. %
  1077. %    o mid_red: Specifies the mid point of the red axis for this node.
  1078. %
  1079. %    o mid_green: Specifies the mid point of the green axis for this node.
  1080. %
  1081. %    o mid_blue: Specifies the mid point of the blue axis for this node.
  1082. %
  1083. %
  1084. */
  1085. static Node *InitializeNode(id,level,parent,mid_red,mid_green,mid_blue)
  1086. unsigned int
  1087.   id,
  1088.   level;
  1089.  
  1090. Node
  1091.   *parent;
  1092.  
  1093. unsigned int
  1094.   mid_red,
  1095.   mid_green,
  1096.   mid_blue;
  1097. {
  1098.   register int
  1099.     i;
  1100.  
  1101.   register Node
  1102.     *node;
  1103.  
  1104.   if (cube.free_nodes == 0)
  1105.     {
  1106.       register Nodes
  1107.         *nodes;
  1108.  
  1109.       /*
  1110.         Allocate a new nodes of nodes.
  1111.       */
  1112.       nodes=(Nodes *) malloc(sizeof(Nodes));
  1113.       if (nodes == (Nodes *) NULL)
  1114.         return((Node *) NULL);
  1115.       nodes->next=cube.node_queue;
  1116.       cube.node_queue=nodes;
  1117.       cube.next_node=nodes->nodes;
  1118.       cube.free_nodes=NodesInAList;
  1119.     }
  1120.   cube.nodes++;
  1121.   cube.free_nodes--;
  1122.   node=cube.next_node++;
  1123.   node->parent=parent;
  1124.   for (i=0; i < 8; i++)
  1125.     node->child[i]=(Node *) NULL;
  1126.   node->id=id;
  1127.   node->level=level;
  1128.   node->census=0;
  1129.   node->mid_red=mid_red;
  1130.   node->mid_green=mid_green;
  1131.   node->mid_blue=mid_blue;
  1132.   node->number_colors=0;
  1133.   node->number_unique=0;
  1134.   node->total_red=0;
  1135.   node->total_green=0;
  1136.   node->total_blue=0;
  1137.   return(node);
  1138. }
  1139.  
  1140. /*
  1141. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
  1142. %                                                                             %
  1143. %                                                                             %
  1144. %                                                                             %
  1145. %  P r u n e C h i l d                                                        %
  1146. %                                                                             %
  1147. %                                                                             %
  1148. %                                                                             %
  1149. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
  1150. %
  1151. %  Function PruneChild deletes the given node and merges its statistics into
  1152. %  its parent.
  1153. %
  1154. %  The format of the PruneSubtree routine is:
  1155. %
  1156. %      PruneChild(node)
  1157. %
  1158. %  A description of each parameter follows.
  1159. %
  1160. %    o node: pointer to node in color cube tree that is to be pruned.
  1161. %
  1162. %
  1163. */
  1164. static void PruneChild(node)
  1165. register Node
  1166.   *node;
  1167. {
  1168.   register Node
  1169.     *parent;
  1170.  
  1171.   /*
  1172.     Merge color statistics into parent.
  1173.   */
  1174.   parent=node->parent;
  1175.   parent->census&=~(1 << node->id);
  1176.   parent->number_unique+=node->number_unique;
  1177.   parent->total_red+=node->total_red;
  1178.   parent->total_green+=node->total_green;
  1179.   parent->total_blue+=node->total_blue;
  1180.   cube.nodes--;
  1181. }
  1182.  
  1183. /*
  1184. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
  1185. %                                                                             %
  1186. %                                                                             %
  1187. %                                                                             %
  1188. %  P r u n e L e v e l                                                        %
  1189. %                                                                             %
  1190. %                                                                             %
  1191. %                                                                             %
  1192. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
  1193. %
  1194. %  Procedure PruneLevel deletes all nodes at the bottom level of the color
  1195. %  tree merging their color statistics into their parent node.
  1196. %
  1197. %  The format of the PruneLevel routine is:
  1198. %
  1199. %      PruneLevel(node)
  1200. %
  1201. %  A description of each parameter follows.
  1202. %
  1203. %    o node: pointer to node in color cube tree that is to be pruned.
  1204. %
  1205. %
  1206. */
  1207. static void PruneLevel(node)
  1208. register Node
  1209.   *node;
  1210. {
  1211.   register int
  1212.     id;
  1213.  
  1214.   /*
  1215.     Traverse any children.
  1216.   */
  1217.   if (node->census != 0)
  1218.     for (id=0; id < 8; id++)
  1219.       if (node->census & (1 << id))
  1220.         PruneLevel(node->child[id]);
  1221.   if (node->level == cube.depth)
  1222.     PruneChild(node);
  1223. }
  1224.  
  1225. /*
  1226. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
  1227. %                                                                             %
  1228. %                                                                             %
  1229. %                                                                             %
  1230. %  R e d u c e                                                                %
  1231. %                                                                             %
  1232. %                                                                             %
  1233. %                                                                             %
  1234. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
  1235. %
  1236. %  Function Reduce traverses the color cube tree and prunes any node whose
  1237. %  number of colors fall below a particular threshold.
  1238. %
  1239. %  The format of the Reduce routine is:
  1240. %
  1241. %      Reduce(node)
  1242. %
  1243. %  A description of each parameter follows.
  1244. %
  1245. %    o node: pointer to node in color cube tree that is to be pruned.
  1246. %
  1247. %
  1248. */
  1249. static void Reduce(node)
  1250. register Node
  1251.   *node;
  1252. {
  1253.   register unsigned int
  1254.     id;
  1255.  
  1256.   /*
  1257.     Traverse any children.
  1258.   */
  1259.   if (node->census != 0)
  1260.     for (id=0; id < 8; id++)
  1261.       if (node->census & (1 << id))
  1262.         Reduce(node->child[id]);
  1263.   if (node->number_colors <= cube.pruning_threshold)
  1264.     PruneChild(node);
  1265.   else
  1266.     {
  1267.       /*
  1268.         Find minimum pruning threshold.
  1269.       */
  1270.       if (node->number_unique > 0)
  1271.         cube.colors++;
  1272.       if (node->number_colors < cube.next_pruning_threshold)
  1273.         cube.next_pruning_threshold=node->number_colors;
  1274.     }
  1275. }
  1276.  
  1277. /*
  1278. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
  1279. %                                                                             %
  1280. %                                                                             %
  1281. %                                                                             %
  1282. %  R e d u c t i o n                                                          %
  1283. %                                                                             %
  1284. %                                                                             %
  1285. %                                                                             %
  1286. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
  1287. %
  1288. %  Function Reduction repeatedly prunes the tree until the number of nodes
  1289. %  with n2 > 0 is less than or equal to the maximum number of colors allowed
  1290. %  in the output image.  On any given iteration over the tree, it selects
  1291. %  those nodes whose n1  count is minimal for pruning and merges their
  1292. %  color statistics upward. It uses a pruning threshold, ns, to govern
  1293. %  node selection as follows:
  1294. %
  1295. %    ns = 0
  1296. %    while number of nodes with (n2 > 0) > required maximum number of colors
  1297. %      prune all nodes such that n1 <= ns
  1298. %      Set ns to minimum n1 in remaining nodes
  1299. %
  1300. %  When a node to be pruned has offspring, the pruning procedure invokes
  1301. %  itself recursively in order to prune the tree from the leaves upward.
  1302. %  n2,  Sr, Sg,  and  Sb in a node being pruned are always added to the
  1303. %  corresponding data in that node's parent.  This retains the pruned
  1304. %  node's color characteristics for later averaging.
  1305. %
  1306. %  For each node, n2 pixels exist for which that node represents the
  1307. %  smallest volume in RGB space containing those pixel's colors.  When n2
  1308. %  > 0 the node will uniquely define a color in the output image. At the
  1309. %  beginning of reduction,  n2 = 0  for all nodes except a the leaves of
  1310. %  the tree which represent colors present in the input image.
  1311. %
  1312. %  The other pixel count, n1, indicates the total number of colors
  1313. %  within the cubic volume which the node represents.  This includes n1 -
  1314. %  n2  pixels whose colors should be defined by nodes at a lower level in
  1315. %  the tree.
  1316. %
  1317. %  The format of the Reduction routine is:
  1318. %
  1319. %      Reduction(number_colors)
  1320. %
  1321. %  A description of each parameter follows.
  1322. %
  1323. %    o number_colors: This integer value indicates the maximum number of
  1324. %      colors in the quantized image or colormap.  The actual number of
  1325. %      colors allocated to the colormap may be less than this value, but
  1326. %      never more.  Note, the number of colors is restricted to a value
  1327. %      less than or equal to 65536 if the continuous_tone parameter has a
  1328. %      value of zero.
  1329. %
  1330. %
  1331. */
  1332. static void Reduction(number_colors)
  1333. unsigned int
  1334.   number_colors;
  1335. {
  1336.   cube.next_pruning_threshold=1;
  1337.   while (cube.colors > number_colors)
  1338.   {
  1339.     cube.pruning_threshold=cube.next_pruning_threshold;
  1340.     cube.next_pruning_threshold=cube.root->number_colors-1;
  1341.     cube.colors=0;
  1342.     Reduce(cube.root);
  1343.   }
  1344. }
  1345.  
  1346. /*
  1347. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
  1348. %                                                                             %
  1349. %                                                                             %
  1350. %                                                                             %
  1351. %  Q u a n t i z a t i o n E r r o r                                          %
  1352. %                                                                             %
  1353. %                                                                             %
  1354. %                                                                             %
  1355. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
  1356. %
  1357. %  Function QuantizationError measures the difference between the original
  1358. %  and quantized images.  This difference is the total quantization error.
  1359. %  The error is computed by summing over all pixels in an image the distance
  1360. %  squared in RGB space between each reference pixel value and its quantized
  1361. %  value.  These values are computed:
  1362. %
  1363. %    o mean_error_per_pixel:  This value is the mean error for any single
  1364. %      pixel in the image.
  1365. %
  1366. %    o normalized_mean_square_error:  This value is the normalized mean
  1367. %      quantization error for any single pixel in the image.  This distance
  1368. %      measure is normalized to a range between 0 and 1.  It is independent
  1369. %      of the range of red, green, and blue values in the image.
  1370. %
  1371. %    o normalized_maximum_square_error:  Thsi value is the normalized
  1372. %      maximum quantization error for any single pixel in the image.  This
  1373. %      distance measure is normalized to a range between 0 and 1.  It is
  1374. %      independent of the range of red, green, and blue values in your image.
  1375. %
  1376. %
  1377. %  The format of the QuantizationError routine is:
  1378. %
  1379. %      QuantizationError(image)
  1380. %
  1381. %  A description of each parameter follows.
  1382. %
  1383. %    o image: The address of a byte (8 bits) array of run-length
  1384. %      encoded pixel data of your reference image.  The sum of the
  1385. %      run-length counts in the reference image must be equal to or exceed
  1386. %      the number of pixels.
  1387. %
  1388. %
  1389. */
  1390. void QuantizationError(image)
  1391. Image
  1392.   *image;
  1393. {
  1394.   register int
  1395.     i;
  1396.  
  1397.   register RunlengthPacket
  1398.     *p;
  1399.  
  1400.   register unsigned int
  1401.     blue_distance,
  1402.     green_distance,
  1403.     red_distance;
  1404.  
  1405.   unsigned long
  1406.     distance,
  1407.     maximum_error_per_pixel,
  1408.     total_error;
  1409.  
  1410.   /*
  1411.     For each pixel, collect error statistics.
  1412.   */
  1413.   for (i=(-MaxRGB); i <= MaxRGB; i++)
  1414.     cube.squares[i+MaxRGB]=i*i;
  1415.   maximum_error_per_pixel=0;
  1416.   total_error=0;
  1417.   p=image->pixels;
  1418.   for (i=0; i < image->packets; i++)
  1419.   {
  1420.     red_distance=(int) p->red-(int) image->colormap[p->index].red+MaxRGB;
  1421.     green_distance=(int) p->green-(int) image->colormap[p->index].green+MaxRGB;
  1422.     blue_distance=(int) p->blue-(int) image->colormap[p->index].blue+MaxRGB;
  1423.     distance=cube.squares[red_distance]+cube.squares[green_distance]+
  1424.       cube.squares[blue_distance];
  1425.     total_error+=(distance*(p->length+1));
  1426.     if (distance > maximum_error_per_pixel)
  1427.       maximum_error_per_pixel=distance;
  1428.     p++;
  1429.   }
  1430.   /*
  1431.     Compute final error statistics.
  1432.   */
  1433.   image->mean_error_per_pixel=(unsigned int)
  1434.     total_error/(image->columns*image->rows);
  1435.   image->normalized_mean_error=
  1436.     ((double) image->mean_error_per_pixel)/(3.0*(MaxRGB+1)*(MaxRGB+1));
  1437.   image->normalized_maximum_error=((double) maximum_error_per_pixel)/
  1438.     (3.0*(MaxRGB+1)*(MaxRGB+1));
  1439.   NumberColors(image,(FILE *) NULL);
  1440. }
  1441.  
  1442. /*
  1443. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
  1444. %                                                                             %
  1445. %                                                                             %
  1446. %                                                                             %
  1447. %  Q u a n t i z e I m a g e                                                  %
  1448. %                                                                             %
  1449. %                                                                             %
  1450. %                                                                             %
  1451. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
  1452. %
  1453. %  Function QuantizeImage analyzes the colors within a reference image and
  1454. %  chooses a fixed number of colors to represent the image.  The goal of the
  1455. %  algorithm is to minimize the difference between the input and output image
  1456. %  while minimizing the processing time.
  1457. %
  1458. %  The format of the QuantizeImage routine is:
  1459. %
  1460. %      colors=QuantizeImage(image,number_colors,tree_depth,dither)
  1461. %
  1462. %  A description of each parameter follows.
  1463. %
  1464. %    o colors: The QuantizeImage function returns this integer
  1465. %      value.  It is the actual number of colors allocated in the
  1466. %      colormap.  Note, the actual number of colors allocated may be less
  1467. %      than the number of colors requested, but never more.
  1468. %
  1469. %    o image: Specifies a pointer to an Image structure;  returned from
  1470. %      ReadImage.
  1471. %
  1472. %    o number_colors: This integer value indicates the maximum number of
  1473. %      colors in the quantized image or colormap.  The actual number of
  1474. %      colors allocated to the colormap may be less than this value, but
  1475. %      never more.  Note, the number of colors is restricted to a value
  1476. %      less than or equal to 65536 if the continuous_tone parameter has a
  1477. %      value of zero.
  1478. %
  1479. %    o tree_depth: Normally, this integer value is zero or one.  A zero or
  1480. %      one tells Quantize to choose a optimal tree depth of
  1481. %      Log4(number_colors).  A tree of this depth generally allows the best
  1482. %      representation of the reference image with the least amount of memory
  1483. %      and the fastest computational speed.  In some cases, such as an image
  1484. %      with low color dispersion (a few number of colors), a value other than
  1485. %      Log4(number_colors) is required.  To expand the color tree completely,
  1486. %      use a value of 8.
  1487. %
  1488. %    o dither: Set this integer value to something other than zero to
  1489. %      dither the quantized image.  The basic strategy of dithering is to
  1490. %      trade intensity resolution for spatial resolution by averaging the
  1491. %      intensities of several neighboring pixels.  Images which suffer
  1492. %      from severe contouring when quantized can be improved with the
  1493. %      technique of dithering.  Severe contouring generally occurs when
  1494. %      quantizing to very few colors, or to a poorly-chosen colormap.
  1495. %      Note, dithering is a computationally expensive process and will
  1496. %      increase processing time significantly.
  1497. %
  1498. %    o colorspace: An unsigned integer value that indicates the colorspace.
  1499. %      Empirical evidence suggests that distances in YUV or YIQ correspond to
  1500. %      perceptual color differences more closely than do distances in RGB
  1501. %      space.  The image is then returned to RGB colorspace after color
  1502. %      reduction.
  1503. %
  1504. %
  1505. */
  1506. void QuantizeImage(image,number_colors,tree_depth,dither,colorspace)
  1507. Image
  1508.   *image;
  1509.  
  1510. unsigned int
  1511.   number_colors,
  1512.   tree_depth,
  1513.   dither,
  1514.   colorspace;
  1515. {
  1516.   Nodes
  1517.     *nodes;
  1518.  
  1519.   unsigned int
  1520.     adjust;
  1521.  
  1522.   /*
  1523.     Reduce the number of colors in the continuous tone image.
  1524.   */
  1525.   if (number_colors > MaxColormapSize)
  1526.     number_colors=MaxColormapSize;
  1527.   if (image->packets == (image->columns*image->rows))
  1528.     CompressImage(image);
  1529.   adjust=0;
  1530.   if (dither)
  1531.     adjust++;
  1532.   if (((float) image->packets/(float) (image->columns*image->rows)) >= 0.9)
  1533.     adjust++;
  1534.   InitializeCube(image->columns*image->rows,number_colors,tree_depth,adjust);
  1535.   if (colorspace != RGBColorspace)
  1536.     RGBTransformImage(image,colorspace);
  1537.   Classification(image);
  1538.   Reduction(number_colors);
  1539.   Assignment(image,number_colors,dither,colorspace);
  1540.   if (colorspace != RGBColorspace)
  1541.     TransformRGBImage(image,colorspace);
  1542.   /*
  1543.     Release color cube tree storage.
  1544.   */
  1545.   do
  1546.   {
  1547.     nodes=cube.node_queue->next;
  1548.     (void) free((char *) cube.node_queue);
  1549.     cube.node_queue=nodes;
  1550.   }
  1551.   while (cube.node_queue != (Nodes *) NULL);
  1552. }
  1553.  
  1554. /*
  1555. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
  1556. %                                                                             %
  1557. %                                                                             %
  1558. %                                                                             %
  1559. %   Q u a n t i z e I m a g e s                                               %
  1560. %                                                                             %
  1561. %                                                                             %
  1562. %                                                                             %
  1563. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
  1564. %
  1565. %  QuantizeImages analyzes the colors within a set of reference images and
  1566. %  chooses a fixed number of colors to represent the set.  The goal of the
  1567. %  algorithm is to minimize the difference between the input and output images
  1568. %  while minimizing the processing time.
  1569. %
  1570. %  The format of the QuantizeImages routine is:
  1571. %
  1572. %      QuantizeImages(images,number_images,number_colors,tree_depth,dither)
  1573. %
  1574. %  A description of each parameter follows:
  1575. %
  1576. %    o images: Specifies a pointer to a set of Image structures.
  1577. %
  1578. %    o number_images:  Specifies an unsigned integer representing the number
  1579. %      images in the image set.
  1580. %
  1581. %    o colormap_image: Specifies a pointer to a Image structure.  Reduce
  1582. %      images to a set of colors represented by this image.
  1583. %
  1584. %    o number_colors: This integer value indicates the maximum number of
  1585. %      colors in the quantized image or colormap.  The actual number of colors
  1586. %      allocated to the colormap may be less than this value, but never more.
  1587. %      Note, the number of colors is restricted to a value less than or equal
  1588. %      to 65536 if the quantized image is not DirectClass.
  1589. %
  1590. %    o tree_depth: Normally, this integer value is zero or one.  A zero or
  1591. %      one tells QUANTIZE to choose a optimal tree depth.  An optimal depth
  1592. %      generally allows the best representation of the reference image with the
  1593. %      fastest computational speed and the least amount of memory.  However,
  1594. %      the default depth is inappropriate for some images.  To assure the best
  1595. %      representation, try values between 2 and 8 for this parameter.
  1596. %
  1597. %    o dither: Set this integer value to something other than zero to
  1598. %      dither the quantized image.  The basic strategy of dithering is to
  1599. %      trade intensity resolution for spatial resolution by averaging the
  1600. %      intensities of several neighboring pixels.  Images which suffer
  1601. %      from severe contouring when quantized can be improved with the
  1602. %      technique of dithering.  Severe contouring generally occurs when
  1603. %      quantizing to very few colors, or to a poorly-chosen colormap.
  1604. %      Note, dithering is a computationally expensive process and will
  1605. %      increase processing time significantly.
  1606. %
  1607. %    o colorspace: An unsigned integer value that indicates the colorspace.
  1608. %      Empirical evidence suggests that distances in YUV or YIQ correspond to
  1609. %      perceptual color differences more closely than do distances in RGB
  1610. %      space.  The image is then returned to RGB colorspace after color
  1611. %      reduction.
  1612. %
  1613. %
  1614. */
  1615. void QuantizeImages(images,number_images,colormap_image,number_colors,
  1616.   tree_depth,dither,colorspace)
  1617. Image
  1618.   **images;
  1619.  
  1620. unsigned int
  1621.   number_images;
  1622.  
  1623. Image
  1624.   *colormap_image;
  1625.  
  1626. unsigned int
  1627.   number_colors,
  1628.   tree_depth,
  1629.   dither,
  1630.   colorspace;
  1631. {
  1632.   Nodes
  1633.     *nodes;
  1634.  
  1635.   register unsigned int
  1636.     i;
  1637.  
  1638.   /*
  1639.     Reduce the number of colors in the continuous tone image sequence.
  1640.   */
  1641.   InitializeCube((unsigned int) (~0),number_colors,tree_depth,2);
  1642.   if (colormap_image != (Image *) NULL)
  1643.     {
  1644.       /*
  1645.         Reduce images to a set of colors represented by the colormap image.
  1646.       */
  1647.       if (colorspace != RGBColorspace)
  1648.         RGBTransformImage(colormap_image,colorspace);
  1649.       Classification(colormap_image);
  1650.       if (colorspace != RGBColorspace)
  1651.         TransformRGBImage(colormap_image,colorspace);
  1652.     }
  1653.   else
  1654.     for (i=0; i < number_images; i+=Max((number_images+16) >> 5,1))
  1655.     {
  1656.       if (images[i]->packets == (images[i]->columns*images[i]->rows))
  1657.         CompressImage(images[i]);
  1658.       if (colorspace != RGBColorspace)
  1659.         RGBTransformImage(images[i],colorspace);
  1660.       if (colormap_image == (Image *) NULL)
  1661.         Classification(images[i]);
  1662.     }
  1663.   Reduction(number_colors);
  1664.   for (i=0; i < number_images; i++)
  1665.   {
  1666.     Assignment(images[i],number_colors,dither,colorspace);
  1667.     if (colorspace != RGBColorspace)
  1668.       TransformRGBImage(images[i],colorspace);
  1669.   }
  1670.   /*
  1671.     Release color cube tree storage.
  1672.   */
  1673.   do
  1674.   {
  1675.     nodes=cube.node_queue->next;
  1676.     (void) free((char *) cube.node_queue);
  1677.     cube.node_queue=nodes;
  1678.   }
  1679.   while (cube.node_queue != (Nodes *) NULL);
  1680. }
  1681.